package leet332reconstructitinerary

import (
	"sort"
)

func ReconstructItinerary(journey [][]string) []string {
	// 思路同之前的46题很像，主要是用过的不用
	// 抽线一个方法，该方法接收used参数表示用过的元素，还要接收目标起始元素，用来查询使用
	// 方法就是在当前未用过的集合中找到首元素是目标起始元素，且如果有多个元素使用字母序更小的元素
	result := [][]string{}
	path := []string{}
	// 首先得遍历一遍所有的路径，否则都不知道有多少路径，遍历出来之后再取紫苜蓿更小的路径
	var iterate func(used map[int]bool, target string)
	iterate = func(used map[int]bool, target string) {
		// 如果used已经全部使用了，则append
		if len(used) == len(journey) {
			pathCopy := make([]string, len(path))
			copy(pathCopy, path)
			result = append(result, pathCopy)
			return
		}
		// 从非used的列表里找到target存在的列表
		targetJourney := []sortedJourney{}
		for i := 0; i < len(journey); i++ {
			if used[i] {
				continue
			}
			if journey[i][0] == target {
				targetJourney = append(targetJourney, sortedJourney{
					index: i,
					dest:  journey[i][1],
				})
			}
		}
		// 对targetJourney按照字母序进行排序
		sort.Slice(targetJourney, func(i, j int) bool {
			return targetJourney[i].dest < targetJourney[j].dest
		})
		for _, j := range targetJourney {
			path = append(path, j.dest)
			used[j.index] = true
			// 继续找
			iterate(used, j.dest)
			// 递归栈回来之后恢复path
			path = path[:len(path)-1]
			delete(used, j.index)
		}
	}
	target := "JFK"
	path = append(path, target)
	iterate(map[int]bool{}, target)
	return result[0]
}

type sortedJourney struct {
	index int
	dest  string // 比如 JKF
}
